package patternmining.model.graph.algorithm;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Stack;
import patternmining.model.graph.Edge;
import patternmining.model.graph.Graph;
import patternmining.model.graph.Vertex;

public class DFS{
    Graph graph;
    private Map<Vertex, Iterator<Vertex>> adjacencies;
    private Map<Vertex, Integer> labelStepInVertex;
    private Map<Vertex, Integer> labelStepOutVertex;
    private Collection<Vertex> visitedVertices;
    private int labelCounter;
    private int vertexCounter;
    private int edgeCounter;
    private Stack<Vertex> stack;
    
    public DFS(Graph graph){
        this.graph = graph;
        adjacencies = new HashMap<Vertex, Iterator<Vertex>>();
        labelStepInVertex = new HashMap<Vertex, Integer>();
        labelStepOutVertex = new HashMap<Vertex, Integer>();
        visitedVertices = new HashSet<Vertex>();
        stack = new Stack<Vertex>();
        labelCounter = 0;
        edgeCounter = 0;
    }
    
    public void walkGraph(){
        Iterator<Vertex> vertices = graph.getVertices().iterator();
        Vertex componentStart;
        while( vertices.hasNext() ){
            componentStart = vertices.next();
            if( ! visitedVertices.contains(componentStart) ){
                System.out.println("Component --------------");
                walkComponent(componentStart);
            }
        }
        System.out.println("\nNumber of vertices: " + vertexCounter);
        System.out.println("\nNumber of edges: " + edgeCounter);
    }
    
    private void walkComponent(Vertex componentStart){
        Vertex current, successor, stepOut;
        current = componentStart;
        visitVertex(current);
        stack.push(current);
        adjacencies.put(current, graph.getSuccessors(current).iterator());
        do{
            while(adjacencies.get(current).hasNext()){
                successor = adjacencies.get(current).next();
                if( ! visitedVertices.contains(successor) ){
                    //edges that lead to a new (not visited) vertex, are of type principal
                    visitEdge(graph.getEdge(current, successor),EdgeType.PRINCIPALEDGE);
                    visitVertex(successor);
                    stack.push(successor);
                    current = successor;
                    adjacencies.put(current, graph.getSuccessors(current).iterator());
                }
                else{
                    //analyze for edge type. can be one of 4 types: direct, return, cross, selfloop
                    if( labelStepInVertex.get(current) <= labelStepInVertex.get(successor) ){
                        if (labelStepInVertex.get(current) == labelStepInVertex.get(successor)){
                            visitEdge(graph.getEdge(current, successor),EdgeType.SELFLOOP);
                        }
                        else{
                            visitEdge(graph.getEdge(current, successor),EdgeType.DIRECTEDGE);
                        }
                    }
                    else{
                        if( labelStepOutVertex.containsKey(successor) ){
                            visitEdge(graph.getEdge(current, successor),EdgeType.CROSSEDGE);
                        }
                        else{
                            visitEdge(graph.getEdge(current, successor),EdgeType.RETURNEDGE);
                        }
                    }
                }
            }
            stepOut = stack.pop(); //remove first vertex from stack. can be garantued that it has no more successor (not yet visited)
            labelCounter++; labelStepOutVertex.put(stepOut, labelCounter);
            if(!stack.empty()){
                current = stack.peek();
            } 
        }while(!stack.empty());
    }
    
    private void visitVertex(Vertex vertex){
        System.out.println("Visited Vertex:  " + vertex.toString() );
        labelCounter++;
        vertexCounter++;
        visitedVertices.add(vertex);
        labelStepInVertex.put(vertex, labelCounter);
        
    }
    
    private void visitEdge(Edge edge, EdgeType type){
        System.out.println("" + type + " (" + edge.getOrigin().toString() + "," + edge.getDestination().toString() + ") : " + edge.toString());
        edgeCounter++;
        //check for parallel edges (might be a multigraph) and visit every edge between this edge's origin and destination
        if( graph.existsParalellEdge(edge) ){
            Edge parallel;
            Iterator<Edge> parallelEdges = graph.getParallelEdges(edge).iterator();
            while(parallelEdges.hasNext()){
                parallel = parallelEdges.next();
                System.out.println("Parallel - " + type + " (" + parallel.getOrigin().toString() + "," + parallel.getDestination().toString() + ") : " + parallel.toString());
                edgeCounter++;
            }
        }
    }
    
    private enum EdgeType{
        PRINCIPALEDGE, RETURNEDGE, DIRECTEDGE, CROSSEDGE, SELFLOOP;
    }
    
}